Luận điểm đảo của định lý nhỏ Fermat là không đúng do nó sai với các số Carmichael. Tuy vậy dạng chính xác hơn của định lý là đúng với tên gọi là định lý Lehmer. Định lý đó được phát biểu như sau:

Nếu tồn tại số nguyên a sao cho

a p − 1 ≡ 1 ( mod p ) {\displaystyle a^{p-1}\equiv 1{\pmod {p}}}

và với mọi số nguyên tố q là ước số của p − 1 để

a ( p − 1 ) / q ≢ 1 ( mod p ) {\displaystyle a^{(p-1)/q}\not \equiv 1{\pmod {p}}} ,

thì p là số nguyên tố.

Định lý này tạo nền tảng cho phép kiểm tra Lucas–Lehmer, một phép kiểm tra tính nguyên tố quan trọng.